In networking, Layer 3 refers to the communications protocol that contains the logical address of a client or server station. It is called the “network layer” and contains the address (IP, IPX, etc.) inspected by a router that forwards it through the network. Layer 3 contains a type field so that traffic can be prioritized and forwarded based on message type as well as network destination. Since Layer 3 provides more filtering capabilities, it also adds more overhead than Layer 2 processing.
A Layer 3 switch is a network device that forwards traffic based on Layer 3 information at very high speeds. Traditionally, routers, which inspect Layer 3, have been considerably slower than Layer 2 switches. In order to increase routing speeds, many “cut-through” techniques have been used, which perform an “inspect the first packet at Layer 3 and send the rest at Layer 2” type of processing. Ipsilon's IP Switch and Cabletron's SecureFast switches were pioneers in cut-through switching; however, the MultiProtocol Label Switching (MPLS) protocol is expected to standardize this technique. MPLS is an Internet Engineering Task Force (IETF) standard for routing packets over the Internet.
The more deeply a packet is examined, the more forwarding decisions can be made based upon type of traffic, quality of service and so on. To get to this information means digging into the packet's headers to ferret out the data, which takes processing time.
The Layer 3 network layer establishes the route between the sending and receiving stations. The node to node function of the data link layer (Layer 2) is extended across the entire Internetwork, because a routable protocol contains a network address in addition to a station address. This layer is the switching function of the dial-up telephone system as well as the functions performed by routable protocols such as IP, IPX, SNA and AppleTalk. If all stations are contained within a single network segment, then the routing capability in this layer is not required. Internet hosts use routing tables to compute the Next Hop for an Internet data packet.
As more routing lookup functions were moved from software into the ASIC chips, Layer 3 switches could inspect each packet just like a router at high speed without using proprietary cut-through methods. If a Layer 3 switch supports packet-by-packet inspection and supports routing protocols, it is called a “routing switch” or “switch router.” which simply means “fast router.” For example, Cisco, Inc. calls its high-end routers Gigabit Switch Routers.
An Internet Protocol Version 4 (IPv4) routing table comprises a set of routes, which is updated by routing protocols such as Routing Information Protocol (RIP) or Open Shortest Path First (OSPF). Each route determines the outgoing interface for a set of IP destination addresses, which is represented by an IP address and a subnet mask. Both the IPv4 addresses and the subnet masks are 32-bit numbers.
Routing tables can take many forms. The following is a simple model that can explain most Internet routing. Each entry in a routing table has at least two fields, IP Address Prefix and Next Hop. The Next Hop is the IP address of another host or router that is directly reachable via an Ethernet, serial link, or some other physical connection. The IP Address Prefix specifies a set of destinations for which the routing entry is valid. In order to be in this set, the beginning of the destination IP address must match the IP Address Prefix, which can have from 0 to 32 significant bits. For example, all IP Address Prefix of 128.8.0.0/16 would match any IP Destination Address of the form 128.8.X.X. The syntax “128.8.0.0” represents four 8-bit bytes where the value of each byte is written in decimal form.
If no routing table entries match a packet's Destination Address, the packet is discarded as undeliverable (possibly with a notification to the sender). If multiple routing table entries match, the longest (prefix) match is preferred. The longest match is the entry with the most 1 bits in its Routing Mask.
To avoid needing routing entries for every possible Internet destination, most hosts and routers use a default route (some routing tables contain nothing but a single default route). A default route has a Routing Address/Mask pair of 0.0.0.0/0.0.0.0. In other words, it matches every IP address, but since there are no 1 bits in its Routing Mask, any other match would be selected by the longest match rule. The default route will only be used if there are no other matches in the routing table, thus its name. Default routes are quite common, and are put to best use on networks with only a single link connecting to the global Internet. On such a network, routing tables will have entries for local nets and sub-nets, as well as a single default route leading to the outbound link. However, remember that all Next Hops must be directly reachable, so the default routes won't necessarily point to the same IP address. Also, some networks (large Internet service providers, mostly) use default free routing tables that must be able to match every IP address in the global net.
A router uses the destination address of every incoming packet to decide the proper Next Hop information of the packet. High-speed routers are required to make these decisions at speeds of several million packets per second. Each search finds the longest prefix match of the destination address among all stored prefixes in the router.
An essential task of a router is to find out the outgoing interface of each incoming packet by querying its routing table, which may consist of more than 30.000 entries in a typical Internet backbone router. In the near future, the number of entries is expected to increase by almost an order of magnitude. In today's high end routers, routing table lookup is the performance bottleneck even though the system back plane (or switch fabric) is running at several times the lookup speed. To remove the bottleneck of table lookup a high-performance router is required to perform IP routing table lookup at the speed of the routers back plane throughput, which is translated into more than 4 million lookups per second for a 2 Gigabit per second backplane.
OC(Optical Carrier)48 defines transmission speeds of the SONET specification as 2488.32 Mbps. The newer OC192 specification increases these transmission speeds to 9953.28 Mbps. As speeds on the Internet move to the speeds of OC192 from OC48, it becomes more difficult to do the table lookups in the router at transmission speeds without resorting to higher speed memory (e.g., changing from DRAM to SRAM). As stated earlier, the router forwarding tables are getting increasingly large, therefore, to store all the routing information in high speed memory would add cost to the routers. The memory size may be reduced by using compression techniques and by finding ways to decrease the amount of data store without reducing performance of the high speed routers.
Associated with this increase from OC48 to OC192 speeds are new requirements resulting from the hardware design constraint of being able to access a given DRAM bank only once per frame. Given that a Longest Prefix Match (LPM) tree search may require two memory accesses, one read to obtain the pattern contained in the forwarding data for the “compare at end” operation and a second read to back track to the previous node (sometimes called the “bird”) if the compare fails, normal OC48 operation cannot directly scale to the higher OC192 speeds and still maintain wire speed.
This single, simple requirement of maintaining wire speed for Layer 3 forwarding forces a redesign of the Layer 3 data structures to fit into the Tree Search Engine (TSE) memory access budget. To solve this problem, one may take the obvious step of moving to faster memory (e.g. SRAM). However, very fast SRAM requires an unrealistically large amount of memory and is too costly in terms of board real-estate, system power and overall product cost.
There is, therefore, a need for a method and device to improve the performance of the table look-up in high speed routers while minimizing cost.